﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm
{
    public static class QuickSort
    {
        /// <summary>
        /// 快速排序，原地排序，最坏情况为 n^2,最佳划分情况下为n * lgn，平均时间复杂度为 n * lgn
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        public static void QuickSortArray<T>(T[] array) where T : IComparable<T>
        {
            QuickSortT<T>(array, 0, array.Length-1);
        }

        public static void QuickSortT<T>(T[] array, int start, int end) where T : IComparable<T>
        {
            if (start < end)
            {
                int m = Partition<T>(array, start, end);
                QuickSortT<T>(array, start, m-1);
                QuickSortT<T>(array, m +1, end);
            }
        }

        /// <summary>
        /// 分组array 从p 到 r 的元素，最终结果为小于的在左边，大于的在右边
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        /// <param name="p"></param>
        /// <param name="r"></param>
        /// <returns></returns>
        private static int Partition<T>(T[] array, int p, int r) where T : IComparable<T>
        {
            T tmp = array[r];
            int i = p - 1;

            for (int j = p; j < r; j++)
            {
                if (array[j].CompareTo(tmp) <= 0)
                {
                    i++;
                    Helper.Exchange<T>(array, i, j);
                }
            }
            Helper.Exchange<T>(array, i+1, r);
            return i + 1;
        }
    }
}
